package bst;

import java.util.ArrayList;
import java.util.Iterator;

public class BST<E extends Comparable<E>> extends AbstractTree<E>  {
    
	protected TreeNode<E> root;
	protected int size=0;
	
	public BST() {
		
	}
	
	
	public BST(E[] objects) {
		
		for(int i=0;i<objects.length;i++) {
			insert(objects[i]);
		}
		
	}
	
	
	@Override
	/**
	 * 寻找某个元素，找到返回true，反之返回false
	 */
	public boolean search(E e) {
		TreeNode<E> current=root;
		while(current!=null) {
			if(e.compareTo(current.element)<0)
				current=current.left;
			else if(e.compareTo(current.element)>0) {
				current=current.right;
			}
			else
				return true;
			
		}
		return false;
	}
	
	public boolean insert(E e) {
		
		if(root==null)
			root=new TreeNode<>(e);
		else {
			
			TreeNode<E> parent=null;
			TreeNode<E> current=root;
			while(current!=null) {
				if(e.compareTo(current.element)<0) {
					parent=current;
					current=current.left;
				}
				else if(e.compareTo(current.element)>0) {
					parent=current;
					current=current.right;
				}
				else
					return false;
			}
			
			if(e.compareTo(parent.element)>0)
				parent.right= new TreeNode(e);
			else
				parent.left=new TreeNode(e);
		}
		
		
		size++;
		return true;
		
		
		
		
		
	}

	@Override
	public boolean delete(E e) {
		
		TreeNode<E> parent=null;
		TreeNode<E> current=root;
		
		while(current!=null) {
			
			if(e.compareTo(current.element)<0) {
				parent=current;
				current=current.left;
			}
			else if(e.compareTo(current.element)>0) {
				parent=current;
				current=current.right;
			}
			else
				 break;
			
		}
		if(current==null)
			return false;
		
		if(current.left==null) {
			
			if(parent==null) {
				root=current.right;
			}
			
			if(e.compareTo(parent.element)>0)
				parent.right=current.right;
			else
				parent.left=current.right;
			
			
			
		}
		else {
			
			TreeNode<E> rightsMost=current.left;
			TreeNode<E> parentOfRightMost=current;
			
			while(rightsMost.right!=null) {
				
				parentOfRightMost=rightsMost;
				rightsMost=rightsMost.right;
				
			}
			
			current.element=rightsMost.element;
			if(parentOfRightMost.right==rightsMost)
				parentOfRightMost.right=rightsMost.left;
			else
				parentOfRightMost.left=rightsMost.left;
				
			
			
			
			
		}
		
		
		
		size--;
		
		
		return true;
	}

	@Override
	public int getSize() {
		// TODO 自动生成的方法存根
		return size;
	}

	
	/**
	 * 使用中序遍历法遍历BST
	 */
	public void inorder() {
		inorder(root);
	}
	
	protected void inorder(TreeNode<E> root) {
		if(root==null) return;
		inorder(root.left);
		System.out.println(root.element);
		inorder(root.right);
	}
	/**
	 * 使用后序遍历法遍历BST
	 */
	public void postorder() {
		postorder(root);
	}
	
	protected void postorder(TreeNode<E> root) {
		if(root==null) return;
		postorder(root.left);
		postorder(root.right);
		System.out.println(root.element);
		
	}
	/**
	 * 使用前序遍历法遍历BST
	 */
	public void preorder() {
		preorder(root);
	}
	
	protected void preorder(TreeNode<E> root) {
		System.out.println(root.element);
		preorder(root.left);
		preorder(root.right);
	}
	 
	
	public TreeNode<E> getRoot(){
		return root;
	}
	
	public ArrayList<TreeNode<E>> path(E e){
		ArrayList<TreeNode<E>> list=new ArrayList<>();
		TreeNode<E> current=root;
		while(current!=null) {
			list.add(current);
			if(e.compareTo(current.element)>0) {
				
				current=current.right;
			}
			else if(e.compareTo(current.element)<0) {
				
				current=current.left;
			}
			else {
				
				break;
			}
		}
		
		
		
		
		
		return list;
	}
	
	
	@Override
	public Iterator<E> iterator() {
		// TODO 自动生成的方法存根
		return new InorderIterator();
	}
	
	private class InorderIterator implements java.util.Iterator<E> {
		
		
		int current=0;
		ArrayList<E> list= new ArrayList<>();
		
		public InorderIterator() {
			
		}
		
		private void Inorder() {
			Inorder(root);
		}
		
		private void Inorder(TreeNode<E> root) {
			Inorder(root.left);
			list.add(root.element);
			Inorder(root.right);
		}

		@Override
		public boolean hasNext() {
			if(current<list.size())
				return true;
			else
				return false;
		}

		@Override
		public E next() {
			return list.get(current++);
		}
		
		public void remove() {
			delete(list.get(current));
			list.clear();
			Inorder();
		}
		
	}
	
	public void clear() {
		
		root=null;
		size=0;
	}
	
	
	public static class TreeNode<E extends Comparable<E>>{
		public  E element;
		public TreeNode<E> left;
		public TreeNode<E> right;
		
		public TreeNode(E e) {
			element=e;
		}
		
	}

}
